#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 定义链表节点
typedef struct Node {
    int data;
    int min_t;
    struct Node* next;
} Node;

typedef struct {
    Node*  sentinel;
} MinStack;

MinStack* minStackCreate() {
    MinStack* stack = (MinStack*)malloc(sizeof(MinStack));
    stack-> sentinel = (Node*)malloc(sizeof(Node)); // 哨兵节点
    stack-> sentinel->next = NULL;
    return stack;
}

void minStackPush(MinStack* obj, int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = val;

    // 计算新节点的min_t：如果栈为空，min_t为val；否则取val与当前栈顶min_t的较小值
    if (obj-> sentinel->next == NULL) {
        newNode->min_t = val;
    } else {
        int current_min = obj-> sentinel->next->min_t;
        newNode->min_t = (val < current_min) ? val : current_min;
    }

    // 将新节点插入链表头部
    newNode->next = obj-> sentinel->next;
    obj-> sentinel->next = newNode;
}

void minStackPop(MinStack* obj) {
    if (obj-> sentinel->next == NULL) return; // 栈空，直接返回
    Node* temp = obj-> sentinel->next;
    obj-> sentinel->next = temp->next;
    free(temp);
}

int minStackTop(MinStack* obj) {
    if (obj-> sentinel->next == NULL) return INT_MIN; // 栈空，返回最小值
    return obj-> sentinel->next->data;
}

int minStackGetMin(MinStack* obj) {
    if (obj-> sentinel->next == NULL) return INT_MIN; // 栈空，返回最小值
    return obj-> sentinel->next->min_t;
}

void minStackFree(MinStack* obj) {
    Node* current = obj-> sentinel->next;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    free(obj-> sentinel);
    free(obj);
}

// 打印栈状态的辅助函数
void printStack(MinStack* obj) {
    printf("栈内容 (顶->底): ");
    Node* current = obj-> sentinel->next;
    while (current != NULL) {
        printf("%d(%d) ", current->data, current->min_t);
        current = current->next;
    }
    printf("\n");
}

int main() {
    printf("创建MinStack...\n");
    MinStack* stack = minStackCreate();
    
    printf("\n测试1: 空栈操作\n");
    printf("栈顶元素: %d\n", minStackTop(stack));
    printf("最小值: %d\n", minStackGetMin(stack));
    
    printf("\n测试2: 添加元素\n");
    minStackPush(stack, 3);
    printf("压入 3 后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    minStackPush(stack, 5);
    printf("压入 5 后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    minStackPush(stack, 2);
    printf("压入 2 后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    minStackPush(stack, 1);
    printf("压入 1 后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    minStackPush(stack, 4);
    printf("压入 4 后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    printf("\n测试3: 弹出元素\n");
    minStackPop(stack);
    printf("弹出后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    minStackPop(stack);
    printf("弹出后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    minStackPop(stack);
    printf("弹出后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    printf("\n测试4: 边界情况\n");
    minStackPop(stack);
    printf("弹出后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    minStackPop(stack);
    printf("弹出后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    // 尝试在空栈上弹出
    minStackPop(stack);
    printf("空栈弹出后: ");
    printStack(stack);
    
    printf("\n测试5: 重新添加元素\n");
    minStackPush(stack, 10);
    printf("压入 10 后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    minStackPush(stack, 5);
    printf("压入 5 后: ");
    printStack(stack);
    printf("栈顶元素: %d, 最小值: %d\n", minStackTop(stack), minStackGetMin(stack));
    
    printf("\n释放栈...\n");
    minStackFree(stack);
    
    printf("测试完成!\n");
    return 0;
}